#include "player.h"

#include <string.h>

#include <QDebug>
#include <chrono>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
using std::endl;
using std::pair;
using std::string;
using std::to_string;
using std::vector;

Human::Human(int _color, Board* board) {
    type = 0;
    color = _color;
    this->board = board;
}

pair<int, int> Human::aiPick() {
    return pair<int, int>(0, 0);
}

void Ai::initPatterns() {
    // 成连五
    blackPatterns["bbbbb"] = 999999;
    // 活四
    blackPatterns["0bbbb0"] = 10000;
    // 冲四
    blackPatterns["0bbbb"] = 5000;
    blackPatterns["b0bbb"] = 4000;
    blackPatterns["bb0bb"] = 5000;
    blackPatterns["bbb0b"] = 4000;
    blackPatterns["bbbb0"] = 5000;
    // 活三
    blackPatterns["0bbb0"] = 500;
    blackPatterns["wbb0bb0"] = 150;  // 奇怪的棋型
    blackPatterns["0b0bb0"] = 100;
    blackPatterns["0bb0b0"] = 100;
    // 眠三
    blackPatterns["00bbbw"] = 100;
    blackPatterns["wbbb00"] = 50;
    blackPatterns["0b0bbw"] = 50;
    blackPatterns["wbb0b0"] = 50;
    blackPatterns["0bb0bw"] = 60;
    blackPatterns["wb00bb"] = 60;
    blackPatterns["wbb00b"] = 60;
    blackPatterns["wb00bb"] = 60;
    // 活二
    blackPatterns["0b0b0"] = 25;
    blackPatterns["00bb00"] = 65;
    // 眠二
    blackPatterns["000bbw"] = 20;
    blackPatterns["wbb000"] = 20;
    blackPatterns["wb0b00"] = 20;
    blackPatterns["00b0bw"] = 20;
    // 有待改进...

    // 给whitePatterns赋值
    for (const auto& entry : blackPatterns) {
        string temp = entry.first;
        for (int i = 0; i < (int)temp.length(); i++) {
            if (temp[i] == 'b') {
                temp[i] = 'w';
            } else if (temp[i] == 'w') {
                temp[i] = 'b';
            }
        }

        whitePatterns[temp] = entry.second;
    }
}

Ai::Ai(int _color, int difficulty, Board* board) : difficulty(difficulty) {
    initPatterns();
    type = 1;
    color = _color;
    this->board = board;
    //    memset(score, 0, sizeof(score));  //初始化score
}

int Player::getType() {
    return this->type;
}

int Player::getColor() {
    return this->color;
}

bool Player::move(int x, int y) {
    if (x < 0 or x >= kBoardSizeNum or y >= kBoardSizeNum or y < 0)  // 如果越界，落子失败
        return 0;

    if (board->getStatus(x, y) != 0)  // 如果那个地方有棋子了，落子失败
        return 0;

    board->setStatus(x, y, color);  // 如果可以落子，那么那个地方就下一个与当前player相符的棋子
    return true;
}

// 优化这里
int Ai::getScore() {
    int res = 0;

    // get string of all four directions
    vector<string> strings;
    // get rows
    for (int i = 0; i < kBoardSizeNum; i++) {
        string temp;
        for (int j = 0; j < kBoardSizeNum; j++) {
            temp += ntc(board->getStatus(i, j));
        }
        strings.emplace_back(std::move(temp));
    }

    // get columns
    for (int i = 0; i < kBoardSizeNum; i++) {
        string temp;
        for (int j = 0; j < kBoardSizeNum; j++) {
            temp += ntc(board->getStatus(j, i));
        }
        strings.emplace_back(std::move(temp));
    }

    // get lower-left -> upper-right
    for (int i = 4; i < kBoardSizeNum; i++) {
        string temp1, temp2;
        for (int j = 0; j < i + 1; j++) {
            temp1 += ntc(board->getStatus(0 + j, i - j));
            temp2 += ntc(board->getStatus(14 - j, 14 - i + j));
        }
        strings.emplace_back(std::move(temp1));
        if (i == 14) break;  // 防止重复加入对角线
        strings.emplace_back(std::move(temp2));
    }

    // get lower-right -> upper-left
    for (int i = 4; i < kBoardSizeNum; i++) {
        string temp1, temp2;
        for (int j = 0; j < i + 1; j++) {
            temp1 += ntc(board->getStatus(14 - (i - j), j));
            temp2 += ntc(board->getStatus(j, 14 - (i - j)));
        }
        strings.emplace_back(std::move(temp1));
        if (i == 14) break;  // 防止重复加入对角线
        strings.emplace_back(std::move(temp2));
    }

    // evaluate each string
    for (const auto& str : strings) {
        int black = evaluate(str, 1);
        int white = evaluate(str, -1);
        // if (black > 40000) {
        //     qDebug() << "Hey!\n";
        // } else {
        //     qDebug() << "Okay..\n";
        // }
        res += (black - white);
    }

    return res;
}

char Ai::ntc(const int& n) {
    if (n == 1) return 'b';
    if (n == -1) return 'w';
    return '0';
}

int Ai::evaluate(const string& str, int color) {
    auto start = std::chrono::high_resolution_clock::now();
    int ret = 0;
    for (const auto& entry : color == 1 ? blackPatterns : whitePatterns) {
        // qDebug() << "pattern: " << entry.first.data() << "\n txt: " << str.data() << endl;
        ret += KMPSearch(entry.first, str) * entry.second;
    }
    qDebug() << "time: " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now() - start).count() << "ms\n";
    return ret;
}

// 根据difficulty搜索
std::pair<int, int> Ai::aiPick() {
    startDepth = difficulty;
    numSearch = 0;
    minimax(pair<int, int>(kBoardSizeNum / 2, kBoardSizeNum / 2), difficulty,
            std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), color);
    qDebug() << numSearch << endl;
    return color == 1 ? maxBest : minBest;
}

int Ai::minimax(const pair<int, int>& pos, int depth, int a, int b, int color) {
    numSearch++;
    if (depth == 0 || board->rule(pos.first, pos.second) != 0) {
        return getScore();
    }

    // get search range
    int up = kBoardSizeNum - 1;
    int down = 0;
    int left = kBoardSizeNum - 1;
    int right = 0;
    for (int i = 0; i < kBoardSizeNum; i++) {
        for (int j = 0; j < kBoardSizeNum; j++) {
            if (board->getStatus(i, j) != 0) {
                if (i < up) up = i;
                if (i > down) down = i;
                if (j < left) left = j;
                if (j > right) right = j;
            }
        }
    }
    up - 3 < 0 ? up = 0 : up -= 3;
    down + 3 > kBoardSizeNum - 1 ? down = kBoardSizeNum - 1 : down += 3;
    left - 3 < 0 ? left = 0 : left -= 3;
    right + 3 > kBoardSizeNum - 1 ? right = kBoardSizeNum - 1 : right += 3;

    if (color == 1) {  // max
        int max = std::numeric_limits<int>::min();
        for (int i = 0; i < kBoardSizeNum; i++) {
            for (int j = 0; j < kBoardSizeNum; j++) {
                if (board->getStatus(i, j) == 0 && i > up &&
                    i < down && j > left && j < right) {  // within search range
                    board->setStatus(i, j, 1);
                    int eval = minimax(pair<int, int>(i, j), depth - 1, a, b, -1);
                    board->setStatus(i, j, 0);
                    if (b < eval) return eval;
                    max = std::max(max, eval);
                    a = std::max(a, eval);
                    if (depth == startDepth && a == eval) maxBest = pair<int, int>(i, j);  // gloabl best result
                }
            }
        }
        return max;
    } else {  // min
        int min = std::numeric_limits<int>::max();
        for (int i = 0; i < kBoardSizeNum; i++) {
            for (int j = 0; j < kBoardSizeNum; j++) {
                if (board->getStatus(i, j) == 0 && i > up &&
                    i < down && j > left && j < right) {  // within search range
                    board->setStatus(i, j, -1);
                    int eval = minimax(pair<int, int>(i, j), depth - 1, a, b, 1);
                    //                    if (eval < 40000) {
                    //                        qDebug() << "Hey!\n";
                    //                    }
                    board->setStatus(i, j, 0);
                    if (eval < a) return eval;
                    min = std::min(min, eval);
                    b = std::min(b, eval);
                    if (depth == startDepth && b == eval) minBest = pair<int, int>(i, j);  // gloabl best result
                }
            }
        }
        return min;
    }
}

void Ai::computeLPSArray(string pat, int M, int lps[]) {
    // Length of the previous longest
    // prefix suffix
    int len = 0;
    int i = 1;
    lps[0] = 0;  // lps[0] is always 0

    // The loop calculates lps[i] for
    // i = 1 to M-1
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else  // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];

                // Also, note that we do not
                // increment i here
            } else  // if (len == 0)
            {
                lps[i] = len;
                i++;
            }
        }
    }
}

int Ai::KMPSearch(string pat, string txt) {
    int M = pat.length();
    int N = txt.length();

    // Create lps[] that will hold the longest
    // prefix suffix values for pattern
    int lps[M];
    int j = 0;  // index for pat[]

    // Preprocess the pattern (calculate lps[]
    // array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    int res = 0;

    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            // When we find pattern first time,
            // we iterate again to check if there
            // exists more pattern
            j = lps[j - 1];
            res++;
        }

        // Mismatch after j matches
        else if (i < N && pat[j] != txt[i]) {
            // Do not match lps[0..lps[j-1]]
            // characters, they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }

    return res;
}

Player::~Player(){};

// std::pair<int, int> Ai::aiPick() {
//     qDebug() << " 传进评分时" << this->getColor() << endl;
//     int MAX = 0;
//     int MIN = 0;
//     int temp_score[15][15] = {{0}};
//     pair<int, int> p;  // 返回位置

//     if (color == -1) board->revert();

//     for (int i = 0; i < 15; i++) {
//         for (int j = 0; j < 15; j++) {
//             getScore(i, j);
//             if (score[i][j] >= MAX)
//                 MAX = score[i][j];
//             temp_score[i][j] = score[i][j];
//         }
//     }

//     memset(score, 0, sizeof(score));

//     if (color == -1) board->revert();

//     for (int i = 0; i < 15; i++) {
//         for (int j = 0; j < 15; j++) {
//             getScore(i, j);
//             if (score[i][j] >= MIN)
//                 MIN = score[i][j];
//         }
//     }

//     if (MAX >= MIN) {
//         MIN = 0;
//         for (int i = 0; i < 15; i++)
//             for (int j = 0; j < 15; j++) {
//                 if (temp_score[i][j] == MAX)
//                     if (score[i][j] >= MIN) {
//                         MIN = score[i][j];
//                         p.first = i;
//                         p.second = j;
//                     }
//             }
//     } else {
//         int MAX = 0;
//         for (int i = 0; i < 15; i++)
//             for (int j = 0; j < 15; j++) {
//                 if (score[i][j] == MIN)
//                     if (score[i][j] >= MAX) {
//                         MAX = score[i][j];
//                         p.first = i;
//                         p.second = j;
//                     }
//             }
//     }

//     memset(score, 0, sizeof(score));
//     qDebug() << " 评分时" << this->getColor() << endl;
//     return p;
// }

// int Ai::getScore() {
//     if (board->getStatus(x, y) != 0) return;

//     board->setStatus(x, y, 1);
//     string all[4];

//     int temp_x = x - 4;  //相当于改变坐标系原点
//     int temp_y = y;
//     for (int i = 0; i < 8; i++)  //竖排
//         if (temp_x + i >= 0 && temp_y >= 0 && temp_x + i < 15 && temp_y < 15) {
//             all[0] += to_string(board->getStatus(temp_x + i, temp_y));
//             if (board->getStatus(temp_x + i, temp_y) == -1)
//                 all[0] += "-";  // 对方的棋子
//         }

//     temp_x = x;
//     temp_y = y - 4;
//     for (int i = 0; i < 8; i++)  //横排
//         if (temp_x >= 0 && temp_y + i >= 0 && temp_x < 15 && temp_y + i < 15) {
//             all[1] += to_string(board->getStatus(temp_x, temp_y + i));
//             if (board->getStatus(temp_x, temp_y + i) == -1)
//                 all[1] += "-";
//         }

//     temp_x = x - 4;
//     temp_y = y + 4;
//     for (int i = 0; i < 8; i++)  //"/"
//         if (temp_x + i >= 0 && temp_y - i >= 0 && temp_x + i < 15 && temp_y - i < 15) {
//             all[2] += to_string(board->getStatus(temp_x + i, temp_y - i));
//             if (board->getStatus(temp_x + i, temp_y - i) == -1)
//                 all[2] += "-";
//         }

//     temp_x = x - 4;
//     temp_y = y - 4;
//     for (int i = 0; i < 8; i++)  //"\"
//         if (temp_x + i >= 0 && temp_y + i >= 0 && temp_x + i < 15 && temp_y + i < 15) {
//             all[3] += to_string(board->getStatus(temp_x + i, temp_y + i));
//             if (board->getStatus(temp_x + i, temp_y + i) == -1)
//                 all[3] += "-";
//         }

// for (int j = 0; j < 4; j++) {
//     size_t IF = all[j].find("11111");  //成连五
//     if (IF != string::npos)
//         score[x][y] += 50000;
//     IF = all[j].find("011110");  //成活四
//     if (IF != string::npos)
//         score[x][y] += 10000;
//     IF = all[j].find("11110");  //成冲四
//     if (IF != string::npos)
//         score[x][y] += 5000;
//     IF = all[j].find("01111");
//     if (IF != string::npos)
//         score[x][y] += 5000;
//     IF = all[j].find("11101");
//     if (IF != string::npos)
//         score[x][y] += 4000;
//     IF = all[j].find("10111");
//     if (IF != string::npos)
//         score[x][y] += 4000;
//     IF = all[j].find("11011");
//     if (IF != string::npos)
//         score[x][y] += 5000;
//     IF = all[j].find("01110");  //成活三
//     if (IF != string::npos)
//         score[x][y] += 500;
//     IF = all[j].find("1011");
//     if (IF != string::npos)
//         score[x][y] += 100;
//     IF = all[j].find("1101");
//     if (IF != string::npos)
//         score[x][y] += 100;
//     IF = all[j].find("00111");  //成眠三
//     if (IF != string::npos)
//         score[x][y] += 50;
//     IF = all[j].find("11100");
//     if (IF != string::npos)
//         score[x][y] += 50;
//     IF = all[j].find("01011");
//     if (IF != string::npos)
//         score[x][y] += 50;
//     IF = all[j].find("11010");
//     if (IF != string::npos)
//         score[x][y] += 50;
//     IF = all[j].find("01101");
//     if (IF != string::npos)
//         score[x][y] += 50;
//     IF = all[j].find("-110110");
//     if (IF != string::npos)
//         score[x][y] += 50;
//     IF = all[j].find("10011");
//     if (IF != string::npos)
//         score[x][y] += 60;
//     IF = all[j].find("11001");
//     if (IF != string::npos)
//         score[x][y] += 60;
//     IF = all[j].find("01010");  //成活二
//     if (IF != string::npos)
//         score[x][y] += 25;
//     IF = all[j].find("001100");
//     if (IF != string::npos)
//         score[x][y] += 65;
//     IF = all[j].find("000110");  //成眠二
//     if (IF != string::npos)
//         score[x][y] += 20;
//     IF = all[j].find("011000");
//     if (IF != string::npos)
//         score[x][y] += 20;
//     IF = all[j].find("00101");
//     if (IF != string::npos)
//         score[x][y] += 20;
//     IF = all[j].find("10100");
//     if (IF != string::npos)
//         score[x][y] += 20;
//     IF = all[j].find("010");
//     if (IF != string::npos)
//         score[x][y] += 25;
//     IF = all[j].find("01");
//     if (IF != string::npos)
//         score[x][y] += 20;
//     IF = all[j].find("1");
//     if (IF != string::npos)
//         score[x][y] += 20;
//     IF = all[j].find("100");
//     if (IF != string::npos)
//         score[x][y] += 25;
//     IF = all[j].find("001");
//     if (IF != string::npos)
//         score[x][y] += 25;
//     IF = all[j].find("00100");
//     if (IF != string::npos)
//         score[x][y] += 25;
// }
//     board->setStatus(x, y, 0);
// }
